package leetcode.weekly.week340;

//Solution4Test
public class Solution5 {

	int m, n;
	int[][] grid;

	public int minimumVisitedCells(int[][] grid) {
		m = grid.length;
		n = grid[0].length;
		this.grid = grid;
		Integer[][] dp = new Integer[m][n];
		Integer ans = f(0, 0, dp);
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	private int f(int x, int y, Integer[][] dp) {
		if (x == m - 1 && y == n - 1) {
			return 1;
		}
		if (dp[x][y] != null) {
			return dp[x][y];
		}
		int size = this.grid[x][y];
		if (size == 0) {

		}
		int ans = Integer.MAX_VALUE;
		for (int i = 1; i <= size; i++) {
			int to = i + y;
			if (to == n) {
				break;
			}
			ans = Math.min(ans, f(x, to, dp));
		}
		for (int i = 1; i <= size; i++) {
			int to = i + x;
			if (to == m) {
				break;
			}
			ans = Math.min(ans, f(to, y, dp));
		}
		if (ans == Integer.MAX_VALUE) {
			dp[x][y] = Integer.MAX_VALUE;
			return ans;
		}
		dp[x][y] = ans + 1;
		return ans + 1;
	}

}
